class Solution {
    //按摩师
    public int massage(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;//特殊情况
        //创建dp表
        int[] f = new int[n];//选
        int[] g = new int[n];//不选
        //初始化
        f[0] = nums[0];
        //填表
        for(int i = 1; i < n; i++){
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(g[i-1], f[i-1]);
        }
        return Math.max(f[n-1], g[n-1]);
    }
    //打家劫舍II
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        return Math.max(fun(nums, 0, n-2), fun(nums, 1, n-1));
    }
    public int fun(int[] nums, int left, int right){
        if(left > right) return 0;
        int n = nums.length;
        //创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        //初始化
        f[left] = nums[left];
        for(int i = left + 1; i <= right; i++){
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1], g[i-1]);
        }
        return Math.max(f[right], g[right]);
    }
    //删除并获得点数
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int len = 10001;
        int[] arr = new int[len];
        //预处理
        for(int index : nums){
            arr[index] += index;
        }
        //创建dp表
        int[] f = new int[len];
        int[] g = new int[len];
        //初始化
        f[0] = arr[0];
        //填表
        for(int i = 1; i < len; i++){
            f[i] = g[i-1] + arr[i];
            g[i] = Math.max(f[i-1], g[i-1]);
        }
        return Math.max(f[len - 1], g[len - 1]);
    }
    //粉刷房子
    public int minCost(int[][] costs) {
        int n = costs.length;
        //创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        int[] h = new int[n];
        //初始化
        f[0] = costs[0][0];
        g[0] = costs[0][1];
        h[0] = costs[0][2];
        //填表
        for(int i = 1; i < n; i++){
            f[i] = Math.min(g[i-1], h[i-1]) + costs[i][0];
            g[i] = Math.min(f[i-1], h[i-1]) + costs[i][1];
            h[i] = Math.min(f[i-1], g[i-1]) + costs[i][2];
        }
        return Math.min(Math.min(f[n-1], g[n-1]), h[n-1]);
    }
    //买卖股票的最佳时期含冷冻期
    public int maxProfit(int[] prices) {
        int n = prices.length;
        //创建dp表
        int[] f = new int[n];//买入
        int[] g = new int[n];//冷冻
        int[] h = new int[n];//可交易
        //初始化
        f[0] = -prices[0];
        //填表
        for(int i = 1; i < n; i++){
            f[i] = Math.max(h[i-1]-prices[i], f[i-1]);
            g[i] = f[i-1] + prices[i];
            h[i] = Math.max(h[i-1], g[i-1]);
        }
        return Math.max(Math.max(f[n-1], g[n-1]), h[n-1]);
    }
    //买卖股票的最佳时机含手续费
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        //创建dp表
        int[] f = new int[n];//买入
        int[] g = new int[n];//可交易
        //初始化
        f[0] = -prices[0]-fee;
        //填表
        for(int i = 1; i < n; i++){
            f[i] = Math.max(f[i-1], g[i-1] - prices[i]-fee);
            g[i] = Math.max(f[i-1] + prices[i], g[i-1]);
        }
        return Math.max(f[n-1], g[n-1]);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3, 4, 2};
        System.out.println(solution.rob(nums));
        solution.deleteAndEarn(nums);
    }
}